{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Offshore Wind Farming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objective and Prerequisites\n",
    "\n",
    "In this example, you’ll learn how to solve an offshore wind power generation problem. The goal of the problem is to figure out which underwater cables should be laid to connect an offshore wind farm power network at a minimum cost. We’ll show you how to formulate a mixed-integer programming (MIP) model of this problem using the Gurobi Python API and then find an optimal solution to the problem using the Gurobi Optimizer.\n",
    "\n",
    "This modeling example is at the beginner level, where we assume that you know Python and that you have some knowledge about building mathematical optimization models.\n",
    "\n",
    "**Download the Repository** <br />\n",
    "You can download the repository containing this and other examples by clicking [here](https://github.com/Gurobi/modeling-examples/archive/master.zip). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Motivation\n",
    "\n",
    "Global climate change has already had observable effects on the environment. Glaciers have shrunk, ice on rivers and lakes is breaking up earlier than expected, plant and animal species have  been affected and trees are flowering sooner than expected. The potential future effects of global climate change include more frequent wildfires, longer periods of drought in some regions and an increase in the number, duration and intensity of tropical storms. [1]\n",
    "\n",
    "Climate change mitigation consists of actions to limit the magnitude or rate of global warming and its related effects.\n",
    "The first challenge for climate change mitigation is eliminating the burning of coal, oil and, eventually, natural gas. This is perhaps the most daunting challenge as denizens of richer nations literally eat, wear, work, play and even sleep on the products made from fossil fuels. Also, citizens of developing nations want and arguably deserve the same comforts. There are no perfect solutions for reducing dependence on fossil fuels (for example, carbon neutral biofuels can drive up the price of food and lead to forest destruction, and while nuclear power does not emit greenhouse gases, it does produce radioactive waste). Other alternatives include plant-derived plastics, biodiesel, and wind power. [2]\n",
    "\n",
    "Offshore wind power is the use of wind farms constructed in bodies of water, usually in the ocean, to harvest wind energy to generate electricity. Higher wind speeds are available offshore compared to on land, so offshore wind power’s electricity generation is higher per amount of capacity installed. \n",
    "\n",
    "The advantage of locating wind turbines offshore is that the wind is much stronger off the coasts, and unlike wind over the continent, offshore breezes can be strong in the afternoon, matching the time when people are using the most electricity. Offshore turbines can also be located close to the load centers along the coasts, such as large cities, eliminating the need for new long-distance transmission lines.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Description\n",
    "\n",
    "An offshore wind farm is a collection of wind turbines placed at sea to take advantage of the strong offshore winds. These strong winds produce more electricity, but offshore wind farms are more expensive to install and operate than those on land.\n",
    "\n",
    "We will use a MIP model to reduce part of the cost of building an offshore wind farm. We will compute a plan for how to lay the underwater cables that connect the turbines. These cables are necessary to transfer the power produced by the turbines to land. The plan we compute will minimize the cost to install the underwater cables, while ensuring that each turbine is connected to the shore and each cable has sufficient capacity to handle the electrical current generated.\n",
    "\n",
    "In our example, a wind farm is being built off the west coast of Denmark. There is a power station on the coast where all the electricity must be transferred to be distributed to the electric grid. There are also transfer stations in the wind farm where the power from several turbines can be collected and transferred along a single cable to the shore.\n",
    "\n",
    "There are two factors we must consider when installing the cables. First, there is a fixed cost to lay a cable on the sea floor. This cost is proportional to the distance between the two stations the cable connects. Second, we must consider how much current will flow through the cables. Connections that carry large currents need thick cables. Thick cables are more expensive than thin cables.\n",
    "\n",
    "The goal of this optimization problem is to decide which cables should be laid to connect the wind farm power network at a minimum cost.\n",
    "\n",
    "The model of offshore wind farming optimization problem is an instance of a more general optimization model known as fixed charge network flow problem. Fixed charge network flow problems can be applied to a large number of business problems -for example, in the planning of communication and transport networks.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution Approach\n",
    "\n",
    "Mathematical programming is a declarative approach where the modeler formulates a mathematical optimization model that captures the key aspects of a complex decision problem. The Gurobi Optimizer solves such models using state-of-the-art mathematics and computer science.\n",
    "\n",
    "A mathematical optimization model has five components, namely:\n",
    "\n",
    "* Sets and indices.\n",
    "* Parameters.\n",
    "* Decision variables.\n",
    "* Objective function(s).\n",
    "* Constraints.\n",
    "\n",
    "We now present a MIP formulation for the offshore wind farming problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model Formulation\n",
    "\n",
    "### Sets and Indices\n",
    "\n",
    "$G(V,E)$: Graph that represents the wind farm network, where $V$ is the set of vertices and $E$ is the set of edges. The turbines, transfer stations, and power stations are vertices in the set of vertices $V$ of the graph. The set of potential cables are the edges of the graph. \n",
    "\n",
    "### Parameters\n",
    "\n",
    "$s_{i} \\in \\mathbb{R}$: Power supplied at vertex $i \\in V$. Since turbines supply power,  they are source vertices with $s_{i} > 0$. Transfer stations do not supply or remove power from the network so they have $s_{i} = 0$. The power station on the coast is a sink that remove all power from the wind farm so it has $s_{i} < 0$.\n",
    "\n",
    "$u_{i,j} \\in \\mathbb{R}^+ $: Maximum current capacity a cable can handle from vertex $i \\in V$ to vertex $j \\in V$.\n",
    "\n",
    "$c_{i,j} \\in \\mathbb{R}^+$: Cost per unit of current flow going from vertex $i \\in V$ to vertex $j \\in V$, i.e. the price we must pay to increase the thickness of the cable to handle an increase in current. \n",
    "\n",
    "$f_{i,j} \\in \\mathbb{R}^+$: Fixed cost of laying a cable from vertex $i \\in V$ to vertex $j \\in V$, and is the result of multiplying the distance between vertices by the cost per mile.\n",
    "\n",
    "### Decision Variables\n",
    "\n",
    "$install_{i,j} \\in \\{0, 1 \\}$: This variable is equal to 1 if we lay a cable from vertex $i \\in V$ to vertex $j \\in V$; and 0 otherwise.\n",
    "\n",
    "$flow_{i,j} \\geq 0$: This non-negative continuous variable represents the amount of current flowing from vertex $i \\in V$ to vertex $j \\in V$.\n",
    "\n",
    "The goal of this optimization model is to decide which of these potential edges in the graph should be used at a minimum cost.\n",
    "\n",
    "### Objective Function\n",
    "\n",
    "- **Total costs**. We want to minimize the total cost to install the cables. The term on the left is the variable costs (i.e. those that vary according to the current in the cable). The term on right is the fixed cost to install the cable.\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{Max} \\quad Z = \\sum_{(i,j) \\in E} c_{i,j} \\cdot flow_{i,j} + \\sum_{(i,j) \\in E} f_{i,j} \\cdot install_{i,j} \n",
    "\\tag{0}\n",
    "\\end{equation}\n",
    "\n",
    "### Constraints\n",
    "\n",
    "- **Balance**. For each vertex $i \\in V$, we want to ensure the conservation of current in the network.\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{j:(i,j) \\in E} flow_{i,j} - \\sum_{j:(j,i) \\in E} flow_{j,i} = s_{i} \\quad \\forall i \\in V\n",
    "\\tag{1}\n",
    "\\end{equation}\n",
    "\n",
    "- **Capacity**. For each edge $(i,j) \\in E$, we want to enforce the limits on the maximum current capacity of each cable.\n",
    "\n",
    "\\begin{equation}\n",
    "0 \\leq flow_{i,j} \\leq u_{i,j} \\cdot install_{i,j}  \\quad \\forall (i,j) \\in E\n",
    "\\tag{2}\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python Implementation\n",
    "\n",
    "This example considers three turbines, one transfer station, and two power stations. The current flowing out at each vertex of the wind farm network is presented in the following table. Recall that since turbines supply power their capacity is positive. Transfer stations do not supply or remove power from the network so they have a capacity of zero.  The power stations on the coast are sinks that remove all power from the wind farm network so they have demand of power, in this case we use a negative number.\n",
    "\n",
    "| <i></i> | Capacity in MW |  \n",
    "| --- | --- | \n",
    "| vertex 1 | 4 |\n",
    "| vertex 2 | 3 |\n",
    "| vertex 3 | 2 |\n",
    "| vertex 4 | 0 |\n",
    "| vertex 5 | -6 |\n",
    "| vertex 6 | -3 |\n",
    "\n",
    "\n",
    "The capacity, flow cost, and fixed cost of each edge in the wind farm network are provided in the following table.\n",
    "\n",
    "| <i></i> | Capacity in MW  | Flow cost in millions of Euros | Fixed cost in millions of Euros| \n",
    "| --- | --- | --- | --- |\n",
    "| Edge: (0,4) | 4 | 1 | 1 |\n",
    "| Edge: (0,3) | 2 | 1 | 1 |\n",
    "| Edge: (1,3) | 3 | 1 | 1 |\n",
    "| Edge: (2,5) | 2 | 1 | 1 |\n",
    "| Edge: (3,4) | 2 | 1 | 1 |\n",
    "| Edge: (3,5) | 1 | 1 | 1 |\n",
    "\n",
    "\n",
    "We now import the Gurobi Python Module. Then, we initialize the data structures with the given data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install gurobipy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gurobipy as gp\n",
    "from gurobipy import GRB\n",
    "\n",
    "# Parameters\n",
    "\n",
    "vertices = {0: 4, 1: 3, 2: 2, 3: 0, 4: -6, 5: -3}\n",
    "edges, cap, flow_cost, fixed_cost = gp.multidict({\n",
    "    (0,4): [4,1,1],\n",
    "    (0,3): [2,1,1],\n",
    "    (1,3): [3,1,1],\n",
    "    (2,5): [2,1,1],\n",
    "    (3,4): [2,1,1],\n",
    "    (3,5): [1,1,1]\n",
    "})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Model Deployment\n",
    "\n",
    "We now determine the MIP model for the offshore wind farming problem, by defining the decision variables, constraints, and objective function. Next, we start the optimization process and Gurobi finds the plan to lay cables at the offshore wind farming network that minimizes total costs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Using license file c:\\gurobi\\gurobi.lic\n",
      "Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)\n",
      "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n",
      "Optimize a model with 12 rows, 12 columns and 24 nonzeros\n",
      "Model fingerprint: 0x03b3989f\n",
      "Variable types: 6 continuous, 6 integer (6 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 4e+00]\n",
      "  Objective range  [1e+00, 1e+00]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [2e+00, 6e+00]\n",
      "Presolve removed 12 rows and 12 columns\n",
      "Presolve time: 0.00s\n",
      "Presolve: All rows and columns removed\n",
      "\n",
      "Explored 0 nodes (0 simplex iterations) in 0.01 seconds\n",
      "Thread count was 1 (of 8 available processors)\n",
      "\n",
      "Solution count 1: 17 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000%\n"
     ]
    }
   ],
   "source": [
    "# MIP  model formulation\n",
    "\n",
    "m = gp.Model(\"offshore_wind_farming\")\n",
    "\n",
    "# Add variables\n",
    "install = m.addVars(edges, vtype=GRB.BINARY, name=\"Install\")\n",
    "flow = m.addVars(edges, vtype=GRB.CONTINUOUS, name=\"Flow\")\n",
    "\n",
    "# Add constraints\n",
    "m.addConstrs((flow.sum(v,'*') - flow.sum('*',v) == supply for v, supply in vertices.items()), name=\"Flow_conservation\")\n",
    "m.addConstrs((flow[e] <= cap[e]*install[e] for e in edges), name=\"Install2flow\")\n",
    "\n",
    "# Set objective\n",
    "m.setObjective(flow.prod(flow_cost) + install.prod(fixed_cost), GRB.MINIMIZE)\n",
    "\n",
    "m.optimize()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Analysis\n",
    "\n",
    "\n",
    "The result of the optimization model shows that the minimum total cost value is 17 million Euros. Let's see the solution that achieves that optimal result.\n",
    "\n",
    "### Cable Installation Plan\n",
    "\n",
    "This plan determines the layout of cables in the offshore wind farming network."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Install cable from location 1 to location 5 in the offshore wind farming network \n",
      "Install cable from location 2 to location 4 in the offshore wind farming network \n",
      "Install cable from location 3 to location 6 in the offshore wind farming network \n",
      "Install cable from location 4 to location 5 in the offshore wind farming network \n",
      "Install cable from location 4 to location 6 in the offshore wind farming network \n"
     ]
    }
   ],
   "source": [
    "# display which edges in the offshore wind farming network we plan to install.\n",
    "\n",
    "for origin, end in install.keys():\n",
    "    if (abs(install[origin, end].x) > 0.5):\n",
    "        print(f\"Install cable from location {origin + 1} to location {end + 1} in the offshore wind farming network \")\n",
    "        \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cable Capacity Plan \n",
    "\n",
    "This plan determines the current flow capacity in MW of each cable installed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The capacity of cable installed from location 1 to location 5 is 4.0 MW \n",
      "The capacity of cable installed from location 2 to location 4 is 3.0 MW \n",
      "The capacity of cable installed from location 3 to location 6 is 2.0 MW \n",
      "The capacity of cable installed from location 4 to location 5 is 2.0 MW \n",
      "The capacity of cable installed from location 4 to location 6 is 1.0 MW \n"
     ]
    }
   ],
   "source": [
    "# Current flow capacity of each cable installed\n",
    "\n",
    "for origin, end in flow.keys():\n",
    "    if (abs(flow[origin, end].x) > 1e-6):\n",
    "         print(f\"The capacity of cable installed from location {origin + 1} to location {end + 1} is {flow[origin, end].x} MW \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Conclusion\n",
    "\n",
    "In this example, we addressed an offshore wind farming problem where we want to minimize the cost of laying underwater cables to collect electricity produced by an offshore wind farm network. We learned how to formulate the problem as a MIP model. Also, we learned how to implement the MIP model formulation and solve it using the Gurobi Python API."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "[1] https://climate.nasa.gov/effects/\n",
    "\n",
    "[2] https://www.scientificamerican.com/article/10-solutions-for-climate-change/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Copyright © 2020 Gurobi Optimization, LLC"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
